翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

deduction theorem : ウィキペディア英語版
deduction theorem
In mathematical logic, the deduction theorem is a metatheorem of first-order logic.〔Kleene 1967, p. 39, 112; Shoenfield 1967, p. 33〕 It is a formalization of the common proof technique in which an implication ''A'' → ''B'' is proved by assuming ''A'' and then deriving ''B'' from this assumption conjoined with known results. The deduction theorem explains why proofs of conditional sentences in mathematics are logically correct. Though it has seemed "obvious" to mathematicians literally for centuries that proving B from A conjoined with a set of theorems is sufficient to proving the implication ''A'' → ''B'' based on those theorems alone, it was left to Herbrand and Tarski to show (independently) this was logically correct in the general case—another instance, perhaps, of modern logic "cleaning up" mathematical practice.
The deduction theorem states that if a formula ''B'' is deducible from a set of assumptions \Delta \cup \, where ''A'' is a closed formula, then the implication ''A'' → ''B'' is deducible from \Delta \,. In symbols, \Delta \cup \ \vdash B
implies \Delta \vdash A \to B \,.. In the special case where \Delta \, is the empty set, the deduction theorem shows that \ \vdash B implies \vdash A \to B.
The deduction theorem holds for all first-order theories with the usual deductive systems for first-order logic. However, there are first-order systems in which new inference rules are added for which the deduction theorem fails.〔Kohlenbach 2008, p. 148〕
The deduction rule is an important property of Hilbert-style systems because the use of this metatheorem leads to much shorter proofs than would be possible without it. Although the deduction theorem could be taken as primitive rule of inference in such systems, this approach is not generally followed; instead, the deduction theorem is obtained as an admissible rule using the other logical axioms and modus ponens. In other formal proof systems, the deduction theorem is sometimes taken as a primitive rule of inference. For example, in natural deduction, the deduction theorem is recast as an introduction rule for "→".
==Examples of deduction==
"Prove" axiom 1:
*
*''P'' 1. hypothesis
*
*
*''Q'' 2. hypothesis
*
*
*''P'' 3. reiteration of 1
*
*''Q''→''P'' 4. deduction from 2 to 3
*''P''→(''Q''→''P'') 5. deduction from 1 to 4 QED
"Prove" axiom 2:
*
*''P''→(''Q''→''R'') 1. hypothesis
*
*
*''P''→''Q'' 2. hypothesis
*
*
*
*''P'' 3. hypothesis
*
*
*
*''Q'' 4. modus ponens 3,2
*
*
*
*''Q''→''R'' 5. modus ponens 3,1
*
*
*
*''R'' 6. modus ponens 4,5
*
*
*''P''→''R'' 7. deduction from 3 to 6
*
*(''P''→''Q'')→(''P''→''R'') 8. deduction from 2 to 7
*(''P''→(''Q''→''R''))→((''P''→''Q'')→(''P''→''R'')) 9. deduction from 1 to 8 QED
Using axiom 1 to show ((''P''→(''Q''→''P''))→''R'')→''R'':
*
*(''P''→(''Q''→''P''))→''R'' 1. hypothesis
*
*''P''→(''Q''→''P'') 2. axiom 1
*
*''R'' 3. modus ponens 2,1
*((''P''→(''Q''→''P''))→''R'')→''R'' 4. deduction from 1 to 3 QED

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「deduction theorem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.